/**
 * 需求: 打印杨辉三角 <br>
 * <p>
 * 比如如输入 3,输出   <br>
 * 1                 <br>
 * 1  1              <br>
 * 1  2  1           <br>
 * <hr>
 * 算法: 二项式系数定理, yangHuiTriangle[i][j] = yangHuiTriangle[i-1][j-1] + yangHuiTriangle[i-1][j]
 * <br>
 * 时间复杂度: O(n^2), n 为行数
 * <br>
 * 空间复杂度: O(1)
 * <p>
 * 知识点: 杨辉三角, 二项式系数
 * <br>
 *
 * @author yonxao
 * @since 2022/5/28
 */
class YangHuiTriangle {
    public static void main(String[] args) {
        lotteryArray();
        System.out.println();
        yangHuiTriangle(3);
    }

    /**
     * 算法: yangHuiTriangle[i][j] = yangHuiTriangle[i-1][j-1] + yangHuiTriangle[i-1][j]
     * 时间复杂度: O(n^2)
     * <br>
     * 空间复杂度: O(1)
     * <p>
     * 知识点: 杨辉三角
     */
    public static void yangHuiTriangle(int n) {

        // 初始化杨辉三角二维数组
        int[][] yangHuiTriangle = new int[n][];
        for (int i = 0; i < n; i++) {
            yangHuiTriangle[i] = new int[i + 1];
            // 首末元素赋值为 1
            yangHuiTriangle[i][0] = 1;
            if (n > 1) {
                yangHuiTriangle[i][i] = 1;
            }
        }

        // 赋值
        for (int row = 2; row < yangHuiTriangle.length; row++) {
            for (int i = 1; i < yangHuiTriangle[row].length - 1; i++) {
                yangHuiTriangle[row][i] = yangHuiTriangle[row - 1][i - 1] + yangHuiTriangle[row - 1][i];
            }
        }

        // 遍历杨辉三角
        for (int[] row : yangHuiTriangle) {
            for (int e : row) {
                System.out.printf("%4d", e);
            }
            System.out.println();
        }
    }

    /**
     * 出自: [Java核心技术]
     * <p>
     * 算法: 二项式系数
     * 时间复杂度: O(n^2)
     * <br>
     * 空间复杂度: O(1)
     * <p>
     * 知识点: 二项式系数公式
     */
    public static void lotteryArray() {
        final int NMAX = 10;

        // allocate triangular array
        int[][] odds = new int[NMAX + 1][];
        for (int n = 0; n <= NMAX; n++) {
            odds[n] = new int[n + 1];
        }

        // fill triangular array
        for (int n = 0; n < odds.length; n++) {
            for (int k = 0; k < odds[n].length; k++) {
                // 二项式系数: compute binomial coefficient n*(n-1)*(n-2)*...*(n-k+1)/(1*2*3*...*k)
                int lotteryOdds = 1;
                for (int i = 1; i <= k; i++) {
                    lotteryOdds = lotteryOdds * (n - i + 1) / i;
                }
                odds[n][k] = lotteryOdds;
            }
        }

        // print triangular array
        for (int[] row : odds) {
            for (int odd : row) {
                System.out.printf("%4d", odd);
            }
            System.out.println();
        }
    }
}
